package algocasts;

public class P143_PathSumIII {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }


    public int pathSum(TreeNode root, int targetSum) {
        if (root == null)
            return 0;
        return rootSum(root, targetSum)
                + pathSum(root.left, targetSum)
                + pathSum(root.right, targetSum);
    }

    public int rootSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int cnt = 0;
        if (root.val == targetSum) cnt++;
        cnt += rootSum(root.left, targetSum - root.val);
        cnt += rootSum(root.right, targetSum - root.val);
        return cnt;
    }




}
